/* Affiche tous les nombres premiers inférieurs à n
 * par la méthode de la crible d'Eratosthène
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[])
{
    int n = 2000000;
    int limite = (int)sqrt(n);
    
    int * crible = NULL;
    crible = malloc(n * sizeof(int));

    int i = 0, j = 0;

    // Remplissage de la crible par tous les nombres de 2 à n
    crible[0] = 2;
    for(i = 1; i < n; ++i)
        crible[i] = crible[i-1] + 1;
     
    /* On cherche le prochain nombre non rayé (différent de 0)
     * On raye (on met à zero) tous ses multiples de la crible
     * Si le prochain nombre non rayé est > à la racine de n
     * alors, tous les nombres non rayés restants sont des nombres premiers
     */
    for(i = 0; i < n; ++i)
    {
        if((crible[i] != 0) && (crible[i] <= limite)) // Si le nombre n'est pas rayé
        {
            for(j = i+1; j < n; ++j)
            {
                if(crible[j] % crible[i] == 0) // On raye tous ses multiples
                    crible[j] = 0;
            }
               
        }
    }

    // Affichage des nombres premiers trouvés
    for(i = 0; i < n; ++i)
    {
        if(crible[i] != 0)
            printf("%d\n", crible[i]);
    }
    
    free(crible);

    return 0;
}
